#define _CRT_SECURE_NO_WARNINGS 1

class TimeMap {
public:
    TimeMap() {

    }

    void set(string key, string value, int timestamp)
    {
        _mp[key].emplace_back(value, timestamp);
    }

    string get(string key, int timestamp)
    {
        if (_mp.find(key) == _mp.end())
        {
            return "";
        }

        auto comp = [](int x, const std::pair<string, int>& pa) {
            return x < pa.second;
        };

        auto pos = std::upper_bound(_mp[key].begin(), _mp[key].end(), timestamp, comp);

        if (pos == _mp[key].begin())
            return "";
        else
            return (*--pos).first;
    }

private:
    std::unordered_map<string, vector<pair<string, int>>> _mp;
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */